package tree;

import offer.TreeNode;

/**
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 *
 * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 *
 *  输入：root = [1,2,3,4,5,6]
 * 输出：6
 * 示例 2：
 *
 * 输入：root = []
 * 输出：0
 * 示例 3：
 *
 * 输入：root = [1]
 * 输出：1
 */
public class leetCode222_countNodes {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(6);
        leetCode222_countNodes leetCode222_countNodes = new leetCode222_countNodes();
        leetCode222_countNodes.countNodes(root);
    }
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        TreeNode left = root;
        TreeNode right = root;
        int hl = 0;
        int hr = 0;
        while (left != null){
            left = left.left;
            hl++;
        }
        while (right != null){
            right = right.right;
            hr++;
        }
        if (hl == hr) {
            return (int)Math.pow(2,hl) - 1;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
